//暴力枚举做法
//2829.k-avoiding 数组的最小总和
//https://leetcode.cn/problems/determine-the-minimum-sum-of-a-k-avoiding-array/
class Solution {
public:
    int minimumSum(int n, int k) {
        int val = 1;
        int ret = 0;
        unordered_set<int> hash;

        while(n)
        {
            //出现在hash中的数可与当前已算入数组的数相加为target
            if(hash.count(val) == 0)
            {
                ret += val;
                //将可与该数组成k的数丢入hash
                hash.insert(k-val);
                --n;
            }
            ++val;
        }
        return ret;
    }
};


//数学分析
//2834.找出美丽数组的最小和
//https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/?envType=daily-question&envId=2024-03-08
class Solution {
public:
    int minimumPossibleSum(int n, int target) {
        const int MOD = 10e8+7;
        //将数组分为两部分
        //一部分数字是 <target 的 另一部分是 >=target 的
        //假如target=7,此时如果n>3
        //那么 1-3是可选的 4,5,6 不可选 则后面可选 7,8,9,10,11,12.... 直到有n个数即可
        //对于<target的数 即选择 1-target/2 中的数 如果n < target/2 则取n的数
        //即 m = min(target/2,n)
        //对于后面的数 剩余 n-m
        //对于1-m个数，使用等差数列可求出总值 即 (m*(m+1))/2
        //对于后面的值 target,target+1,...,target+n-m-1(后面剩余n-m个数，但不到2*target)=((target*2+n-m-1)*(n-m))/2

        long long m = min(target/2,n);
        //当target==n 则不存在后面的数组，即后面部分为0
        return (m*(m+1)+(n-m-1+target*2)*(n-m))/2%MOD;
    }
};